package codingInterview.leetcode.editor.cn;

//////////找出数组中重复的数字。 
//////////
////////// 
//////////在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数
//字重
////复了
//////几次
////////。请
//////////找出数组中任意一个重复的数字。 
//////////
////////// 示例 1： 
//////////
////////// 输入：
//////////[2, 3, 1, 0, 2, 5, 3]
//////////输出：2 或 3 
////////// 
//////////
////////// 
//////////
////////// 限制： 
//////////
////////// 2 <= n <= 100000 
////////// Related Topics 数组 哈希表 排序 👍 723 👎 0
////////
//////
////
//

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//Java：剑指 Offer 03 - 数组中重复的数字
public class ShuZuZhongZhongFuDeShuZiLcof{
    public static void main(String[] args) {
                Solution solution = new ShuZuZhongZhongFuDeShuZiLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findRepeatNumber(int[] nums) {
        int index=0;
        while(index<nums.length){
            if(nums[index]!=index){ // 不在自己位置上
                if(nums[nums[index]]!=nums[index]){ //该在位置上也不对
                    int tmp = nums[nums[index]];
                    nums[nums[index]]=nums[index];
                    nums[index] = tmp;
                }else{
                    return nums[index];
                }
            }else{
                index++;
            }
        }
        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
